package com.algorithm.learning.binarysearch;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/16 22:21
 **/
public class 搜索旋转排序数组 {

    /**
     * 这个题目的意思是，
     * 有一个升序排序的数组，但是经过旋转后得到一个新的数组，那么根据这个新的数组，再给你一个target，找到target在数组中的位置，不存在就返回-1
     *
     * 例如：有一个升序数组[1,2,3,4,5]，经过旋转后，新数组为[3,4,5,1,2]
     * 那么输入nums = [3,4,5,1,2], target = 1，则返回下标3
     * target = 0, 则返回-1
     *
     * 整体思路不难，依然是根据二分查找确定目标值的区间
     *
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > nums[right]) {
                // 第一种情况，mid值大于right
                // 如果target小于mid，且target大于right，那么target一定在mid的左区间，也就是[left, mid - 1]
                // 这里一定要注意，判断条件，target可能是等于mid，不可能等于right，因为mid是大于right的
                if (target <= nums[mid] && target > nums[right]) {
                    right = mid - 1;
                } else {
                    // 这里要注意left一定是mid + 1, 因为可能存在target == mid
                    left = mid + 1;
                }
            } else {
                // 那么这种情况就是此时target一定在mid的右区间，即[mid + 1, right]
                // 而且target可能是等于right, 不可能是等于mid，因为mid是小于right的
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }

    public static boolean searchForRepeat(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] > nums[right]) {
                // 第一种情况，mid值大于right
                // 如果target小于mid，且target大于right，那么target一定在mid的左区间，也就是[left, mid - 1]
                // 这里一定要注意，判断条件，target可能是等于mid，不可能等于right，因为mid是大于right的
                if (target <= nums[mid] && target > nums[right]) {
                    right = mid - 1;
                } else {
                    // 这里要注意left一定是mid + 1, 因为可能存在target == mid
                    left = mid + 1;
                }
            } else if (nums[mid] == nums[right]) {
                right = right - 1;
            } else {
                // 那么这种情况就是此时target一定在mid的右区间，即[mid + 1, right]
                // 而且target可能是等于right, 不可能是等于mid，因为mid是小于right的
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return nums[left] == target;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,3};
//        System.out.println(search(nums, 3));
        System.out.println(searchForRepeat(nums, 0));
    }

}
